package algorithm.dynamicProgramming;

import java.util.Arrays;

/**
 * @Author CandyWall
 * @Date 2021/4/6--9:41
 * @Description 0-1背包问题
 *                  递归解法
 */
public class Knapsack01_v1 {
    private int[][] memo;

    /**
     *
     * @param w ：物品的重量
     * @param v ：物品的价值
     * @param c ：背包的剩余容量
     * @return
     */
    public int fillKnapsack(int[] w, int[] v, int c) {
        if (w.length != v.length) {
            throw new IllegalArgumentException("记录物品的重量和价值的数组长度不一致！");
        }
        int n = w.length;
        memo = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }

        return bestValue(w, v, n - 1, c);
    }

    // 用[0...index]范围内的物品，填充容积为c的背包的最大价值
    private int bestValue(int[] w, int[] v, int index, int c) {
        if (index < 0 || c <= 0) {
            return 0;
        }

        if (memo[index][c] != -1) {
            return memo[index][c];
        }

        // 选择1：不考虑index位置上的物品，尝试将index之前的物品放入背包
        int res = bestValue(w, v, index - 1, c);
        // 选择2：直接将index位置上的物品放入背包
        if (w[index] <= c) {
            res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
        }
        memo[index][c] = res;

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Knapsack01_v1().fillKnapsack(new int[]{1, 2, 3}, new int[]{6, 10, 12}, 5));
    }
}
